309B - Context Advertising - CodeForces Solution

    #include <bits/stdc++.h>
    using namespace std;

    using ll = long long;
    using pll = pair<long long, long long>;

    #define pb push_back
    #define F first
    #define S second  
    #define all(x) (x)  .begin(), (x).end()
    
    const ll N = 1e6 + 100;
    const ll inf = 1e18;
    const ll mod = 1e9 + 7;
    const ll block = 520;
    const ll base = 35711;
    ll a[N], ps[N], up[N][25], nxt[N];
    string s[N];
    ll n,r,c;
    void build(){
        for(int j = 0; j <= 24;j++) up[n+1][j] = n + 1;
        for(int j = 1; j <= 24;j++){
            for(int i = 1; i <= n;i++){
                up[i][j] = up[up[i][j-1]][j-1];
            }
        }
    }
    void to_nho_cau(){
        cin >> n >> r >> c;
        for(int i = 1; i <= n;i++){
            cin >> s[i];
            ps[i] = ps[i-1] + s[i].size();  
        }
        for(int i = 1; i <= n;i++){
            ll l = i, r = n + 1;
            while(l + 1 < r){
                ll mid = (l + r) / 2;
                if(ps[mid] - ps[i - 1] + (mid - i) <= c) l = mid;
                else r = mid;
            }
            if(s[i].size() > c){
                up[i][0] = i;
            }   
            else{
                up[i][0] = l + 1;
            }
        }
        build();
        ll res = 0;
        for(int i = 1; i <= n;i++){
            ll u = i;
            for(int j = 24; j >= 0;j--) if(r & (1 << j)) u = up[u][j];
            nxt[i] = --u;
            if(s[i].size() <= c) res = max(res, u - i + 1);
        }
        for(int i = 1; i <= n;i++){
            if(nxt[i] - i + 1 == res){
                ll cnt = 0;
                for(int j = i; j <= nxt[i];j++){
                    if(cnt + s[j].size() > c){
                        cnt = 0;    
                        cout << '\n';
                        r--;
                        if(!r) return;
                    }
                    else if(cnt) cout << ' ';
                    cout << s[j];
                    cnt += s[j].size() + 1;
                }
                return;
            }
        }
    }

    signed main()
    {   
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int t = 1;   
        //cin >> t;
        while(t--) to_nho_cau();
    }